package day20210630;

import treenode.SimpleTreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 501. 二叉搜索树中的众数
 *
 * @author lizy
 * @date 2021/06/30
 */
public class Solution2 {

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.left = new SimpleTreeNode(2);
        simpleTreeNode.left.left = new SimpleTreeNode(1);
        simpleTreeNode.left.left.left = new SimpleTreeNode(1);
        System.out.println(Arrays.toString(solution.findMode(simpleTreeNode)));
    }

    List<Integer> answer = new ArrayList<>();
    int base, count, maxCount;

    public int[] findMode(SimpleTreeNode root) {
        dfs(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void dfs(SimpleTreeNode o) {
        if (o == null) {
            return;
        }
        dfs(o.left);
        update(o.val);
        dfs(o.right);
    }

    public void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }

}
